%{
#include <cstdio>
#include <cstring>

// 词法分析头文件
#include "FlexLexer.h"

// bison生成的头文件
#include "BisonParser.h"

// 抽象语法树函数定义原型头文件
#include "AST.h"

// LR分析失败时所调用函数的原型声明
void yyerror(char * msg);

%}

// 联合体声明，用于后续终结符和非终结符号属性指定使用
%union {
    class ast_node * node;
    
    struct digit_int_attr integer_num;
    struct digit_real_attr float_num;
    struct var_id_attr var_id;
};

// 文法的开始符号
%start  CompileUnit

%nonassoc lowerelse
%nonassoc T_ELSE

// 指定文法的终结符号，<>可指定文法属性
// 对于单个字符的算符或者分隔符，在词法分析时可直返返回对应的字符即可
%token <integer_num> T_DIGIT
%token <float_num> T_FLOAT
%token <var_id> T_ID
%token T_FUNC T_RETURN T_IF T_ELSE T_WHILE T_FOR
%token T_MUL T_DIV T_MOD T_ADD T_SUB
%token T_LT T_GT T_LE T_GE T_EQ T_NEQ
%token T_LOG_AND T_LOG_OR T_LOG_NOT
%token T_INCR T_DECR

%type <node> CompileUnit

// 指定文法的非终结符号，<>可指定文法属性
%type <node> FuncDef
%type <node> FuncFormalParams
%type <node> Block

%type <node> FuncFormalParam
%type <node> FuncBasicParam

%type <node> BlockItemList
%type <node> BlockItem

%type <node> Statement
%type <node> Expr optExpr optExprAndVarDecl optExprAndVarDef
%type <node> AddExp MulExp UnaryExp LVal PostfixExp
%type <node> PrimaryExp
%type <node> RealParamList
%type <node> FuncType
%type <node> IType

%type <node> Decl
%type <node> VarDecl FuncDecl
%type <node> VarDefList
%type <node> VarDef
%type <node> InitVal
%type <node> ArrayDef ArrBracket

%type <node> RelExp EqExp LAndExp LOrExp
%type <node> Cond optCond
%type <node> ifStmt

%token <var_id> T_VOID
%token <var_id> T_INT
%token <var_id> T_BREAK T_CONTINUE

%left T_ADD T_SUB
%left T_MUL T_DIV T_MOD

%%

/* 编译单元可包含若干个函数，main函数作为程序的入口，必须存在 */
CompileUnit : FuncDef {
        $$ = create_contain_node(ast_operator_type::AST_OP_COMPILE_UNIT, $1);
        ast_root = $$;
    }
	| Decl {
		$$ = create_contain_node(ast_operator_type::AST_OP_COMPILE_UNIT, $1);
		ast_root = $$;
	}
    | CompileUnit FuncDef {
        $$ = insert_ast_node($1, $2);
    }
	| CompileUnit Decl {
		$$ = insert_ast_node($1, $2);
	}
    ;

// 声明
Decl : VarDecl {
		$$ = $1;
	}
	|
	FuncDecl {
		$$ = $1;
	}
	;


// 变量声明
VarDecl : 
	IType VarDefList ';' {
		$$ = new_ast_node(ast_operator_type::AST_OP_VAR_DECL, $1, $2, nullptr);
	}
	|
	FuncType VarDefList ';' {
		$$ = new_ast_node(ast_operator_type::AST_OP_VAR_DECL, $1, $2, nullptr);
	}
	;

// 声明列表
VarDefList : VarDef {
		$$ = create_contain_node(ast_operator_type::AST_OP_VAR_LIST, $1);
    }
    | VarDefList ',' VarDef {
		$$ = insert_ast_node($1, $3);
    }
    ;

// 函数声明
FuncDecl : FuncType T_ID '(' ')' ';' {
		$$ = create_func_decl($2.lineno, $1, $2.id, nullptr);
	}
    | FuncType T_ID '(' FuncFormalParams ')' ';' {
        $$ = create_func_decl($2.lineno, $1, $2.id, $4);
	}
	| IType T_ID '(' ')' ';' {
		$$ = create_func_decl($2.lineno, $1, $2.id, nullptr);
	}
    | IType T_ID '(' FuncFormalParams ')' ';' {
		$$ = create_func_decl($2.lineno, $1, $2.id, $4);
	}
    ;

// 函数定义
FuncDef : FuncType T_ID '(' ')' Block  {
        $$ = create_func_def($2.lineno, $1, $2.id, $5, nullptr);
        // $$ = create_func_def($2.lineno, $2.id, $5, nullptr);
    }
    | FuncType T_ID '(' FuncFormalParams ')' Block {
        $$ = create_func_def($2.lineno, $1, $2.id, $6, $4);
        // $$ = create_func_def($2.lineno, $2.id, $6, $4);
    }
	| IType T_ID '(' ')' Block  {
        $$ = create_func_def($2.lineno, $1, $2.id, $5, nullptr);
        // $$ = create_func_def($2.lineno, $2.id, $5, nullptr);
    }
    | IType T_ID '(' FuncFormalParams ')' Block {
        $$ = create_func_def($2.lineno, $1, $2.id, $6, $4);
        // $$ = create_func_def($2.lineno, $2.id, $6, $4);
    }
    ;

// 函数参数
FuncFormalParams : FuncFormalParam  {
        $$ = create_contain_node(ast_operator_type::AST_OP_FUNC_FORMAL_PARAMS, $1);
    }
    | FuncFormalParams ',' FuncFormalParam {
        $$ = insert_ast_node($1, $3);
    }
    ;

// 函数参数
FuncFormalParam : FuncBasicParam  {
        $$ = $1;
    }
    ;

// 变量定义
VarDef :
	T_ID {
		$$ = new_ast_leaf_node(var_id_attr{$1.id, $1.lineno});
	}
	|
	T_ID '=' InitVal {
        // $$ = new_ast_node(ast_operator_type::AST_OP_VAR_DEF, $1, $3, nullptr); 
		// 变量节点
		ast_node * id_node = new_ast_leaf_node(var_id_attr{$1.id, $1.lineno});

		free($1.id);

        // 创建一个AST_OP_ASSIGN类型的中间节点，孩子为Id和Expr($3)
        $$ = new_ast_node(ast_operator_type::AST_OP_ASSIGN, id_node, $3, nullptr);
    }
	|
	ArrayDef {
		$$ = $1;
	}
    ;


// 数组定义
ArrayDef :
	ArrayDef '[' Expr ']' {
		$$ = insert_ast_node($1, $3);
	}
	|
    T_ID '[' Expr ']' {
        // 变量节点
		ast_node * id_node = new_ast_leaf_node(var_id_attr{$1.id, $1.lineno});

		free($1.id);

        // 创建一个AST_OP_ASSIGN类型的中间节点，孩子为Id和Expr($3)
        $$ = new_ast_node(ast_operator_type::AST_OP_ARRAY_DEF, id_node, $3, nullptr);
    }
    ;

// 变量初始化
InitVal : Expr {
		$$ = $1; 
}

// 基本类型函数参数，默认整型
FuncBasicParam : IType T_ID {
        $$ = create_func_formal_param($1, $2.lineno, $2.id);
    }
	|
	FuncType T_ID {
		$$ = create_func_formal_param($1, $2.lineno, $2.id);
	}
	|
	IType T_ID '[' ']' {
        $$ = create_func_formal_param($1, $2.lineno, $2.id, true);
    }
	|
	FuncType T_ID '[' ']' {
		$$ = create_func_formal_param($1, $2.lineno, $2.id, true);
	}
    ;

// 语句块
Block : '{' '}' {
        // 语句块没有语句
        $$ = nullptr;
    }
    | '{' BlockItemList '}' {
        // 语句块含有语句
        $$ = $2;
    }
    ;

// 语句块内语句列表
BlockItemList : BlockItem {
        // 第一个左侧的孩子节点归约成Block父节点，后续语句可不断作为孩子追加到block中
        // 创建一个AST_OP_BLOCK类型的中间节点，孩子为Statement($1)
        $$ = new_ast_node(ast_operator_type::AST_OP_BLOCK, $1, nullptr);
    }
    | BlockItemList BlockItem  {
        // 采用左递归的文法产生式，可以使得Block节点在上个产生式创建，后续递归追加孩子节点
        // 请注意，不要采用右递归，左递归翻遍孩子的追加
        // BlockItem($2)作为Block($1)的孩子 
        $$ = insert_ast_node($1, $2);
    }
    ;

// 目前语句块内项目只能是语句
BlockItem : Statement  {
        $$ = $1;
    }
	|
	Decl {
		$$ = $1;
	}
    ;

/* 语句 */
Statement : LVal '=' Expr ';' {
        // 归约到Statement时要执行的语义动作程序
        // 赋值语句，不显示值

        // 创建一个AST_OP_ASSIGN类型的中间节点，孩子为Id和Expr($3)
        $$ = new_ast_node(ast_operator_type::AST_OP_ASSIGN, $1, $3, nullptr);
    }
    |
	Expr ';' {
        // Expr归约到Statement时要执行的语义动作程序
        // 表达式语句，不显示表达式的值

        // 创建一个AST_OP_EXPR类型的中间节点，孩子为Expr($1)
        $$ = new_ast_node(ast_operator_type::AST_OP_EXPR, $1, nullptr);
    }
    |
	Block {
		$$ = $1;
	}
	|
	T_IF '(' Cond ')' Statement ifStmt {
		$$ = new_ast_node(ast_operator_type::AST_OP_IF, $3, $5, $6, nullptr);
	}
	|
	T_WHILE '(' Cond ')' Statement {
		$$ = new_ast_node(ast_operator_type::AST_OP_WHILE, $3, $5, nullptr);
    }
	|
	T_FOR '(' optExprAndVarDecl ';' optCond ';' optExprAndVarDef ')' Statement {
		$$ = new_ast_node(ast_operator_type::AST_OP_FOR, $3, $5, $7, $9, nullptr);
	}
	|
	T_BREAK ';' {
		$$ = new_break_node($1.lineno);
	}
	|
	T_CONTINUE ';' {
		$$ = new_continue_node($1.lineno);
    }
    | 
	T_RETURN Expr ';' {
        // 返回语句
        $$ = new_ast_node(ast_operator_type::AST_OP_RETURN_STATEMENT, $2, nullptr);
    }
	|
	T_RETURN ';' {
        // 返回语句
        $$ = new_ast_node(ast_operator_type::AST_OP_RETURN_STATEMENT, nullptr);
    }
    ;

ifStmt : T_ELSE Statement {
		$$ = $2;
	}
	|
	%prec lowerelse{
		$$ = nullptr;
	}
	;

optExprAndVarDecl : IType VarDefList
	{
		$$ = new_ast_node(ast_operator_type::AST_OP_VAR_DECL, $1, $2, nullptr);
	}
	|
	FuncType VarDefList
	{
		$$ = new_ast_node(ast_operator_type::AST_OP_VAR_DECL, $1, $2, nullptr);
	}
    | optExprAndVarDef
	{
		$$ = $1;
	}
    ;

optExprAndVarDef : LVal '=' Expr {
		$$ = new_ast_node(ast_operator_type::AST_OP_ASSIGN, $1, $3, nullptr);
	}
	|
	optExpr
    {
        $$ = $1;
    }
    ;

optExpr : Expr
	{
		$$ = $1;
	}
    | /* empty */
	{
		$$ = new_ast_node(ast_operator_type::AST_OP_OPT_NULL, nullptr);
	}
    ;

Expr : AddExp {
        $$ = $1;
    }
    ;

optCond : Cond {
		$$ = $1;
	}
	| /* empty */
	{
		$$ = new_ast_node(ast_operator_type::AST_OP_OPT_NULL, nullptr);
	}
    ;

// 条件判断语句
Cond : LOrExp {
		$$ = $1;
	}

// 不等表达式
RelExp : AddExp {
		$$ = $1;
	}
	|
	RelExp T_GT AddExp {
		$$ = new_ast_node(ast_operator_type::AST_REL_GT, $1, $3, nullptr);
	}
	|
	RelExp T_GE AddExp {
		$$ = new_ast_node(ast_operator_type::AST_REL_GE, $1, $3, nullptr);
    }
    |
	RelExp T_LT AddExp {
		$$ = new_ast_node(ast_operator_type::AST_REL_LT, $1, $3, nullptr);
    }
    |
	RelExp T_LE AddExp {
		$$ = new_ast_node(ast_operator_type::AST_REL_LE, $1, $3, nullptr);
    }
    ;

// 相等性表达式
EqExp : RelExp {
		$$ = $1;
	}
	|
	EqExp T_EQ RelExp {
		$$ = new_ast_node(ast_operator_type::AST_REL_EQ, $1, $3, nullptr);
    }
    |
	EqExp T_NEQ RelExp {
		$$ = new_ast_node(ast_operator_type::AST_REL_NEQ, $1, $3, nullptr);
    }
    ;

// 逻辑与表达式
LAndExp : EqExp {
		$$ = $1;
	}
	|
	LAndExp T_LOG_AND EqExp {
		$$ = new_ast_node(ast_operator_type::AST_LOG_AND, $1, $3, nullptr);
    }
    ;

// 逻辑或表达式
LOrExp : LAndExp {
		$$ = $1;
    }
	|
	LOrExp T_LOG_OR LAndExp {
		$$ = new_ast_node(ast_operator_type::AST_LOG_OR, $1, $3, nullptr);
    }
    ;

// 消除二义性
/* 加法表达式 */
AddExp : AddExp T_ADD MulExp {
        /* Expr = Expr + Term */

        // 创建一个AST_OP_ADD类型的中间节点，孩子为Expr($1)和Term($3)
        $$ = new_ast_node(ast_operator_type::AST_OP_ADD, $1, $3, nullptr);
    }
    | AddExp T_SUB MulExp {
        /* Expr = Expr + Term */

        // 创建一个AST_OP_ADD类型的中间节点，孩子为Expr($1)和Term($3)
        $$ = new_ast_node(ast_operator_type::AST_OP_SUB, $1, $3, nullptr);
	}
    |
	MulExp {
		$$ = $1;
	}
    ;

/* 乘法/除法表达式 */
MulExp : MulExp T_MUL UnaryExp {
		/* Expr = Expr * Term */

        // 创建一个AST_OP_ADD类型的中间节点，孩子为Expr($1)和Term($3)
        $$ = new_ast_node(ast_operator_type::AST_OP_MUL, $1, $3, nullptr);
	}
	| MulExp T_DIV UnaryExp {
		/* Expr = Expr / Term */

        // 创建一个AST_OP_ADD类型的中间节点，孩子为Expr($1)和Term($3)
        $$ = new_ast_node(ast_operator_type::AST_OP_DIV, $1, $3, nullptr);
	}
	| MulExp T_MOD UnaryExp {
		/* Expr = Expr * Term */

        // 创建一个AST_OP_ADD类型的中间节点，孩子为Expr($1)和Term($3)
        $$ = new_ast_node(ast_operator_type::AST_OP_MOD, $1, $3, nullptr);
	}
	| UnaryExp {
        /* Expr = Term */
        $$ = $1;
    }
	;

UnaryExp : T_SUB UnaryExp {
		// 如果有多重-，可以进行优化
		if ($2->node_type == ast_operator_type::AST_OP_NEG) {
			$$ = $2->sons[0];
		} else {
			$$ = new_ast_node(ast_operator_type::AST_OP_NEG, $2, nullptr);
		}
    }
	|
	T_LOG_NOT UnaryExp {
		// 如果有多重!，可以进行优化
		if ($2->node_type == ast_operator_type::AST_LOG_NOT) {
			$$ = $2->sons[0];
		} else {
			$$ = new_ast_node(ast_operator_type::AST_LOG_NOT, $2, nullptr);
		}
	}
	|
	PostfixExp {
		$$ = $1;
	}
	|
	T_INCR UnaryExp {
		$$ = new_ast_node(ast_operator_type::AST_OP_INCR_PREV, $2, nullptr);
	}
	|
	T_DECR UnaryExp {
		$$ = new_ast_node(ast_operator_type::AST_OP_DECR_PREV, $2, nullptr);
	}
    | T_ID '(' ')' {
        // 用户自定义的不含实参的函数调用
        $$ = create_func_call($1.lineno, $1.id, nullptr);
    }
    | T_ID '(' RealParamList ')' {
        // 用户自定义的含有实参的参数调用
        $$ = create_func_call($1.lineno, $1.id, $3);
    }

PostfixExp : PrimaryExp {
        $$ = $1;
    }
	|
	PostfixExp T_INCR {
		$$ = new_ast_node(ast_operator_type::AST_OP_INCR_POST, $1, nullptr);
	}
	|
	PostfixExp T_DECR {
		$$ = new_ast_node(ast_operator_type::AST_OP_DECR_POST, $1, nullptr);
	}
	;

PrimaryExp :  '(' Cond ')' {
        /* PrimaryExp = Cond */
        $$ = $2;
    }
    | T_DIGIT {

        // 终结符作为抽象语法树的叶子节点进行创建
        $$ = new_ast_leaf_node(digit_int_attr{$1.val, $1.lineno});
    }
	| T_FLOAT {
        // 浮点数数识别

        // 终结符作为抽象语法树的叶子节点进行创建
        $$ = new_ast_leaf_node(digit_real_attr{$1.val, $1.lineno});
    }
    | LVal  {
        // 左值
        $$ = $1;
    }
    ;

LVal : T_ID {
        // 终结符作为抽象语法树的叶子节点进行创建
        $$ = new_ast_leaf_node(var_id_attr{$1.id, $1.lineno});

		// 对于字符型字面量的字符串空间需要释放，因词法用到了strdup进行了字符串复制
		free($1.id);
    }
	|
	T_ID ArrBracket {
        // 变量节点
		ast_node * id_node = new_ast_leaf_node(var_id_attr{$1.id, $1.lineno});

		free($1.id);

        // 创建一个AST_OP_ARRAY_CALL类型的中间节点，孩子为Id和Expr($2)
        $$ = new_ast_node(ast_operator_type::AST_OP_ARRAY_CALL, id_node, $2, nullptr);
    }
	;

ArrBracket : '[' Expr ']' {
		$$ = new_ast_node(ast_operator_type::AST_OP_ARRAY_BRA, $2, nullptr);
	}
	|
	ArrBracket '[' Expr ']' {
		$$ = insert_ast_node($1, $3);
	}

/* 实参列表 */
RealParamList : Expr {
        $$ = create_contain_node(ast_operator_type::AST_OP_FUNC_REAL_PARAMS, $1);
    }
    | RealParamList ',' Expr {
        $$ = insert_ast_node($1, $3);
    }
    ;

FuncType : T_VOID {
		// printf("%s\n", $1.id);
		$$ = new_ast_leaf_node(var_id_attr{$1.id, $1.lineno});
	}

IType : T_INT {
	$$ = new_ast_leaf_node(var_id_attr{$1.id, $1.lineno});
	}
	;


%%

// 语法识别错误要调用函数的定义
void yyerror(char * msg)
{
    printf("Line %d: %s\n", yylineno, msg);
}
